package LearnDataStructure.d_图结构.例题;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-16 18:44
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.例题
 */
/*
...11111111111111111111111111111
11.111111........1111111111.1111
11.111111..111.11111111.....1111
11.11111111111.1111111111.111111
11.111111.................111111
11.111111.11111111111.11111.1111
11.111111.11111111111.11111..111
11..........111111111.11111.1111
11111.111111111111111.11....1111
11111.111111111111111.11.11.1111
11111.111111111111111.11.11.1111
111...111111111111111.11.11.1111
111.11111111111111111....11.1111
111.11111111111111111111111.1111
111.1111.111111111111111......11
111.1111.......111111111.1111.11
111.1111.11111.111111111.1111.11
111......11111.111111111.1111111
11111111111111.111111111.111...1
11111111111111...............1.1
111111111111111111111111111111..

如上图的迷宫，入口，出口分别：左上角，右下角
"1"是墙壁，"."是通路
求最短需要走多少步？
 */
public class d_走迷宫最少步byBFS {
    public static void main(String[] args) {
        d_走迷宫最少步byBFS test = new d_走迷宫最少步byBFS();
        test.useBFS();
    }

    public void useBFS() {
        Scanner scanner = new Scanner(System.in);
        int row = 21;
        int col = 32;
        char[][] graph = new char[row][col];
        int[][] visited = new int[row][col];
        Queue<Node> queue = new LinkedList<Node>();
        for (int i = 0; i < row; i++) {
            graph[i] = scanner.nextLine().toCharArray();
        }
        operateBFS(graph, queue, visited, 0, 0, 20, 31);
    }

    public void operateBFS(char[][] graph, Queue<Node> queue, int[][] visited, int beginX, int beginY, int endX, int endY) {
        Node beginNode = new Node(beginX, beginY, 0);
        queue.add(beginNode);
        //开始穷举，BFS
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int x = node.x;
            int y = node.y;
            visited[x][y] = 1;
            if (x == endX && y == endY) {
                System.out.println(node.depth + "步");
                break;
            }
            /*
            对四个方向进行穷举
            这个BFS能处理“多条路都能走出迷宫”的情况
            因为是波浪形扩散穷举地，所以走的格子少的波浪会先到达endX,endY
            所以此时就输出这个波浪的depth
             */
            if (x - 1 >= 0 && visited[x-1][y] == 0 && graph[x-1][y] == '.') {//左走
                queue.add(new Node(x-1,y,node.depth+1));
            }
            if (x + 1 <= endX && visited[x+1][y] == 0 && graph[x+1][y] == '.') {//右走
                queue.add(new Node(x+1,y,node.depth+1));
            }
            if (y - 1 >= 0 && visited[x][y-1] == 0 && graph[x][y-1] == '.') {//上走
                queue.add(new Node(x,y-1,node.depth+1));
            }
            if (y + 1 <= endY && visited[x][y+1] == 0 && graph[x][y+1] == '.') {//上走
                queue.add(new Node(x,y+1,node.depth+1));
            }
        }
    }

    static class Node {
        int x = 0;
        int y = 0;
        int depth = 0;

        public Node(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
}
